home *** CD-ROM | disk | FTP | other *** search
/ Inter.Net 55-1 / Inter.Net 55-1.iso / CBuilder / Setup / BCB / data.z / tree.cc < prev    next >
Encoding:
C/C++ Source or Header  |  1998-02-09  |  22.8 KB  |  694 lines
  1. #ifndef __TREE_CC
  2. #define __TREE_CC
  3. #pragma option push -b -a4 -Vx- -Ve- -w-inl -w-aus -w-sig
  4.  
  5. /***************************************************************************
  6.  *
  7.  * tree.cc - Non-nline tree definitions for the Standard Library
  8.  *
  9.  * $Id: tree.cc,v 1.9 1996/09/27 22:21:20 smithey Exp $
  10.  *
  11.  ***************************************************************************
  12.  *
  13.  * Copyright (c) 1994
  14.  * Hewlett-Packard Company
  15.  *
  16.  * Permission to use, copy, modify, distribute and sell this software
  17.  * and its documentation for any purpose is hereby granted without fee,
  18.  * provided that the above copyright notice appear in all copies and
  19.  * that both that copyright notice and this permission notice appear
  20.  * in supporting documentation.  Hewlett-Packard Company makes no
  21.  * representations about the suitability of this software for any
  22.  * purpose.  It is provided "as is" without express or implied warranty.
  23.  *
  24.  *
  25.  ***************************************************************************
  26.  *
  27.  * (c) Copyright 1994, 1995 Rogue Wave Software, Inc.
  28.  * ALL RIGHTS RESERVED *
  29.  * The software and information contained herein are proprietary to, and
  30.  * comprise valuable trade secrets of, Rogue Wave Software, Inc., which
  31.  * intends to preserve as trade secrets such software and information.
  32.  * This software is furnished pursuant to a written license agreement and
  33.  * may be used, copied, transmitted, and stored only in accordance with
  34.  * the terms of such license and with the inclusion of the above copyright
  35.  * notice.  This software and information or any other copies thereof may
  36.  * not be provided or otherwise made available to any other person.
  37.  *
  38.  * Notwithstanding any other lease or license that may pertain to, or
  39.  * accompany the delivery of, this computer software and information, the
  40.  * rights of the Government regarding its use, reproduction and disclosure
  41.  * are as set forth in Section 52.227-19 of the FARS Computer
  42.  * Software-Restricted Rights clause.
  43.  *
  44.  * Use, duplication, or disclosure by the Government is subject to
  45.  * restrictions as set forth in subparagraph (c)(1)(ii) of the Rights in
  46.  * Technical Data and Computer Software clause at DFARS 252.227-7013.
  47.  * Contractor/Manufacturer is Rogue Wave Software, Inc.,
  48.  * P.O. Box 2328, Corvallis, Oregon 97339.
  49.  *
  50.  * This computer software and information is distributed with "restricted
  51.  * rights."  Use, duplication or disclosure is subject to restrictions as
  52.  * set forth in NASA FAR SUP 18-52.227-79 (April 1985) "Commercial
  53.  * Computer Software-Restricted Rights (April 1985)."  If the Clause at
  54.  * 18-52.227-74 "Rights in Data General" is specified in the contract,
  55.  * then the "Alternate III" clause applies.
  56.  *
  57.  **************************************************************************/
  58.  
  59. #include <stdcomp.h>
  60.  
  61. #ifndef _RWSTD_NO_NAMESPACE
  62. namespace __rwstd {
  63. #endif
  64.  
  65. template <class Key, class Value, class KeyOfValue, 
  66.           class Compare, class Allocator>
  67. _TYPENAME rb_tree<Key, Value, KeyOfValue, Compare, Allocator>::link_type 
  68. rb_tree<Key, Value, KeyOfValue, Compare, Allocator>::NIL = 0;
  69.  
  70. #ifdef __WIN16__
  71. template <class Key, class Value, class KeyOfValue, 
  72.           class Compare, class Allocator>
  73. _TYPENAME rb_tree<Key, Value, KeyOfValue, Compare, Allocator>::rb_tree_node  
  74. rb_tree<Key, Value, KeyOfValue, Compare, Allocator>::theNilNode = 
  75. rb_tree<Key, Value, KeyOfValue, Compare, Allocator>::rb_tree_node();
  76. #else
  77. template <class Key, class Value, class KeyOfValue, 
  78.           class Compare, class Allocator>
  79. _TYPENAME rb_tree<Key, Value, KeyOfValue, Compare, Allocator>::size_type
  80. rb_tree<Key, Value, KeyOfValue, Compare, Allocator>::number_of_trees = 0;
  81. #endif
  82.  
  83. template <class Key, class Value, class KeyOfValue, 
  84.           class Compare, class Allocator>
  85. void rb_tree<Key, Value, KeyOfValue, Compare, Allocator>::deallocate_buffers ()
  86. {
  87.     while (buffer_list)
  88.     {
  89.         buffer_pointer tmp = buffer_list;
  90.         buffer_list        = (buffer_pointer)(buffer_list->next_buffer);
  91.         node_alloc_type(the_allocator).deallocate(tmp->buffer,tmp->size);
  92.         buffer_alloc_type(the_allocator).deallocate(tmp,1);
  93.     }
  94. }
  95.  
  96. template <class Key, class Value, class KeyOfValue, 
  97.           class Compare, class Allocator>
  98. rb_tree<Key, Value, KeyOfValue, Compare, Allocator>& 
  99. rb_tree<Key, Value, KeyOfValue, Compare, Allocator>::
  100. operator= (const rb_tree<Key, Value, KeyOfValue, Compare, Allocator>& x)
  101. {
  102.     if (!(this == &x))
  103.     {
  104.         //
  105.         // Can't be done as in list because Key may be a constant type.
  106.         //
  107.         erase(begin(), end());
  108.         root() = __copy(x.root(), header);
  109.         if (isNil(root()))
  110.         {
  111.             leftmost()  = header; rightmost() = header;
  112.         }
  113.         else
  114.         {
  115.             leftmost()  = minimum(root()); rightmost() = maximum(root());
  116.         }
  117.         node_count = x.node_count;
  118.     }
  119.     return *this;
  120. }
  121.  
  122. template <class Key, class Value, class KeyOfValue, 
  123.           class Compare, class Allocator>
  124. _TYPENAME rb_tree<Key, Value, KeyOfValue, Compare, Allocator>::iterator
  125. rb_tree<Key, Value, KeyOfValue, Compare, Allocator>::
  126. __insert (link_type x, link_type y, const Value& v)
  127. {
  128.     ++node_count;
  129.     link_type z = get_node(v);
  130.     if (y == header || !isNil(x) || key_compare(KeyOfValue()(v), key(y)))
  131.     {
  132.         left(y) = z;  // Also makes leftmost() = z when y == header.
  133.         if (y == header)
  134.         {
  135.             root() = z; rightmost() = z;
  136.         }
  137.         else if (y == leftmost())
  138.             leftmost() = z;   // Maintain leftmost() pointing to minimum node.
  139.     }
  140.     else
  141.     {
  142.         right(y) = z;
  143.         if (y == rightmost())
  144.             rightmost() = z;  // Maintain rightmost() pointing to maximum node.
  145.     }
  146.     parent(z) = y;
  147.     left(z) = NIL;
  148.     right(z) = NIL;
  149.     x = z;  // Recolor and rebalance the tree.
  150.     color(x) = rb_red;
  151.     while (x != root() && color(parent(x)) == rb_red) 
  152.         if (parent(x) == left(parent(parent(x))))
  153.         {
  154.             y = right(parent(parent(x)));
  155.             if (color(y) == rb_red)
  156.             {
  157.                 color(parent(x))         = rb_black;
  158.                 color(y)                 = rb_black;
  159.                 color(parent(parent(x))) = rb_red;
  160.                 x                        = parent(parent(x));
  161.             }
  162.             else
  163.             {
  164.                 if (x == right(parent(x)))
  165.                 {
  166.                     x = parent(x); 
  167.                     rotate_left(x);
  168.                 }
  169.                 color(parent(x)) = rb_black;
  170.                 color(parent(parent(x))) = rb_red;
  171.                 rotate_right(parent(parent(x)));
  172.             }
  173.         }
  174.         else
  175.         {
  176.             y = left(parent(parent(x)));
  177.             if (color(y) == rb_red)
  178.             {
  179.                 color(parent(x))         = rb_black;
  180.                 color(y)                 = rb_black;
  181.                 color(parent(parent(x))) = rb_red;
  182.                 x                        = parent(parent(x));
  183.             }
  184.             else
  185.             {
  186.                 if (x == left(parent(x)))
  187.                 {
  188.                     x = parent(x); 
  189.                     rotate_right(x);
  190.                 }
  191.                 color(parent(x))         = rb_black;
  192.                 color(parent(parent(x))) = rb_red;
  193.                 rotate_left(parent(parent(x)));
  194.             }
  195.         }
  196.     color(root()) = rb_black;
  197.     return iterator(z);
  198. }
  199.  
  200. template <class Key, class Value, class KeyOfValue, 
  201.           class Compare, class Allocator>
  202. _TYPENAME rb_tree<Key, Value, KeyOfValue, Compare, Allocator>::pair_iterator_bool
  203. rb_tree<Key, Value, KeyOfValue, Compare, Allocator>::insert (const Value& v)
  204. {
  205.     link_type y = header;
  206.     link_type x = root();
  207.     bool _RWSTD_COMP   = true;
  208.     while (!isNil(x))
  209.     {
  210.         y    = x;
  211.         _RWSTD_COMP = key_compare(KeyOfValue()(v), key(x));
  212.         x    = _RWSTD_COMP ? left(x) : right(x);
  213.     }
  214.     if (insert_always)
  215.     {
  216.         pair_iterator_bool tmp(__insert(x, y, v), true); return tmp;
  217.     }
  218.     iterator j = iterator(y);   
  219.     if (_RWSTD_COMP)
  220.     {
  221.         if (j == begin())  
  222.         {
  223.             pair_iterator_bool tmp(__insert(x, y, v), true); return tmp;
  224.         }
  225.         else
  226.             --j;
  227.     }
  228.     if (key_compare(key(j.node), KeyOfValue()(v)))
  229.     {
  230.         pair_iterator_bool tmp(__insert(x, y, v), true); return tmp;
  231.     }
  232.     pair_iterator_bool tmp(j, false);
  233.     return tmp;
  234. }
  235.  
  236. template <class Key, class Value, class KeyOfValue, 
  237.           class Compare, class Allocator>
  238. _TYPENAME rb_tree<Key, Value, KeyOfValue, Compare, Allocator>::iterator 
  239. rb_tree<Key, Value, KeyOfValue, Compare, Allocator>::insert (iterator position,
  240.                                                   const Value& v)
  241. {
  242.     if (position == iterator(begin()))
  243.         if (size() > 0 && key_compare(KeyOfValue()(v), key(position.node)))
  244.             return __insert(position.node, position.node, v);
  245.             //
  246.             // First argument just needs to be non-NIL.
  247.             //
  248.         else
  249.             return insert(v).first;
  250.     else if (position == iterator(end()))
  251.         if (key_compare(key(rightmost()), KeyOfValue()(v)))
  252.             return __insert(NIL, rightmost(), v);
  253.         else
  254.             return insert(v).first;
  255.     else
  256.     {
  257.         iterator before = --position;
  258.         if (key_compare(key(before.node), KeyOfValue()(v))
  259.             && key_compare(KeyOfValue()(v), key(position.node)))
  260.             if (isNil(right(before.node)))
  261.                 return __insert(NIL, before.node, v); 
  262.             else
  263.                 return __insert(position.node, position.node, v);
  264.                 //
  265.                 // First argument just needs to be non-NIL.
  266.                 //
  267.         else
  268.             return insert(v).first;
  269.     }
  270. }
  271.  
  272. #ifndef _RWSTD_NO_MEMBER_TEMPLATES
  273. template <class Key, class Value, class KeyOfValue, 
  274.           class Compare, class Allocator>
  275. template<class Iterator>
  276. void rb_tree<Key, Value, KeyOfValue, Compare, Allocator>::insert (Iterator first, 
  277.                                                        Iterator last)
  278. {
  279.     while (first != last) insert(*first++);
  280. }
  281. #else
  282. template <class Key, class Value, class KeyOfValue, 
  283.           class Compare, class Allocator>
  284. void rb_tree<Key, Value, KeyOfValue, Compare, Allocator>::insert (const_iterator first, 
  285.                                                        const_iterator last)
  286. {
  287.     while (first != last) insert(*first++);
  288. }
  289.  
  290. template <class Key, class Value, class KeyOfValue, 
  291.           class Compare, class Allocator>
  292. void rb_tree<Key, Value, KeyOfValue, Compare, Allocator>::insert (const Value* first, 
  293.                                                        const Value* last)
  294. {
  295.     while (first != last) insert(*first++);
  296. }
  297. #endif
  298.          
  299. template <class Key, class Value, class KeyOfValue, 
  300.           class Compare, class Allocator>
  301. _TYPENAME rb_tree<Key, Value, KeyOfValue, Compare, Allocator>::iterator 
  302. rb_tree<Key, Value, KeyOfValue, Compare, Allocator>::erase (iterator position)
  303. {
  304.     iterator tmp = position; // Retain 'next' position for return
  305.     if (tmp != end())
  306.        tmp++;
  307.  
  308.     link_type z;
  309.     __initialize(z, link_type(position.node));
  310.     link_type y = z;
  311.     link_type x;
  312.     if (isNil(left(y)))
  313.         x = right(y);
  314.     else
  315.         if (isNil(right(y))) 
  316.             x = left(y);
  317.         else
  318.         {
  319.             y = right(y);
  320.             while (!isNil(left(y))) y = left(y);
  321.             x = right(y);
  322.         }
  323.     if (y != z)
  324.     {
  325.         //
  326.         // Relink y in place of z.
  327.         //
  328.         parent(left(z)) = y; 
  329.         left(y) = left(z);
  330.         if (y != right(z))
  331.         {
  332.             parent(x)        = parent(y); // Possibly x == NIL.
  333.             left(parent(y))  = x;         // Y must be a left child.
  334.             right(y)         = right(z);
  335.             parent(right(z)) = y;
  336.         }
  337.         else
  338.             parent(x) = y;  // Needed in case x == NIL.
  339.         if (root() == z)
  340.             root() = y;
  341.         else if (left(parent(z)) == z)
  342.             left(parent(z)) = y;
  343.         else 
  344.             right(parent(z)) = y;
  345.         parent(y) = parent(z);
  346. #ifndef _RWSTD_NO_NAMESPACE
  347.         std::swap(color(y), color(z));
  348. #else
  349.         ::swap(color(y), color(z));
  350. #endif
  351.         y = z; // y points to node to be actually deleted.
  352.     }
  353.     else
  354.     {
  355.         //
  356.         // y == z
  357.         //
  358.         parent(x) = parent(y);   // Possibly x == NIL.
  359.         if (root() == z)
  360.             root() = x;
  361.         else 
  362.             if (left(parent(z)) == z)
  363.                 left(parent(z)) = x;
  364.             else
  365.                 right(parent(z)) = x;
  366.         if (leftmost() == z) 
  367.             if (isNil(right(z)))  // left(z) must be NIL also.
  368.                 leftmost() = parent(z);
  369.                 //
  370.                 // makes leftmost() == header if z == root()
  371.                 //
  372.         else
  373.             leftmost() = minimum(x);
  374.         if (rightmost() == z)  
  375.             if (isNil(left(z))) // right(z) must be NIL also.
  376.                 rightmost() = parent(z);
  377.                 //
  378.                 // makes rightmost() == header if z == root().
  379.                 //
  380.         else
  381.             //
  382.             // x == left(z)
  383.             //
  384.             rightmost() = maximum(x);
  385.     }
  386.     if (color(y) != rb_red)
  387.     { 
  388.         while (x != root() && color(x) == rb_black)
  389.             if (x == left(parent(x)))
  390.             {
  391.                 link_type w = right(parent(x));
  392.                 if (color(w) == rb_red)
  393.                 {
  394.                     color(w)         = rb_black;
  395.                     color(parent(x)) = rb_red;
  396.                     rotate_left(parent(x));
  397.                     w = right(parent(x));
  398.                 }
  399.                 if (color(left(w)) == rb_black && color(right(w)) == rb_black)
  400.                 {
  401.                     color(w) = rb_red;
  402.                     x = parent(x);
  403.                 }
  404.                 else
  405.                 {
  406.                     if (color(right(w)) == rb_black)
  407.                     {
  408.                         color(left(w)) = rb_black;
  409.                         color(w)       = rb_red;
  410.                         rotate_right(w);
  411.                         w = right(parent(x));
  412.                     }
  413.                     color(w) = color(parent(x));
  414.                     color(parent(x)) = rb_black;
  415.                     color(right(w))  = rb_black;
  416.                     rotate_left(parent(x));
  417.                     break;
  418.                 }
  419.             }
  420.             else
  421.             {
  422.                 //
  423.                 // Same as then clause with "right" and "left" exchanged.
  424.                 //
  425.                 link_type w = left(parent(x));
  426.                 if (color(w) == rb_red)
  427.                 {
  428.                     color(w)         = rb_black;
  429.                     color(parent(x)) = rb_red;
  430.                     rotate_right(parent(x));
  431.                     w = left(parent(x));
  432.                 }
  433.                 if (color(right(w)) == rb_black && color(left(w)) == rb_black)
  434.                 {
  435.                     color(w) = rb_red; x = parent(x);
  436.                 }
  437.                 else
  438.                 {
  439.                     if (color(left(w)) == rb_black)
  440.                     {
  441.                         color(right(w)) = rb_black;
  442.                         color(w)        = rb_red;
  443.                         rotate_left(w);
  444.                         w = left(parent(x));
  445.                     }
  446.                     color(w) = color(parent(x));
  447.                     color(parent(x)) = rb_black;
  448.                     color(left(w))   = rb_black;
  449.                     rotate_right(parent(x));
  450.                     break;
  451.                 }
  452.             }
  453.         color(x) = rb_black;
  454.     }
  455.     put_node(y);
  456.     --node_count;
  457.     return tmp;
  458. }
  459.  
  460. template <class Key, class Value, class KeyOfValue, 
  461.           class Compare, class Allocator>
  462. _TYPENAME rb_tree<Key, Value, KeyOfValue, Compare, Allocator>::size_type 
  463. rb_tree<Key, Value, KeyOfValue, Compare, Allocator>::erase (const Key& x)
  464. {
  465.     pair_iterator_iterator p = equal_range(x);
  466.     size_type n;
  467.     __initialize(n, size_type(0));
  468.     distance(p.first, p.second, n);
  469.     erase(p.first, p.second);
  470.     return n;
  471. }
  472.  
  473. template <class Key, class Value, class KeyOfValue, 
  474.           class Compare, class Allocator>
  475. _TYPENAME rb_tree<Key, Value, KeyOfValue, Compare, Allocator>::link_type 
  476. rb_tree<Key, Value, KeyOfValue, Compare, Allocator>::__copy (link_type x, link_type p)
  477. {
  478.    //
  479.    // Structural copy.
  480.    // 
  481.    link_type r = x;
  482.    while (!isNil(x))
  483.    {
  484.       link_type y = get_node(value(x));
  485.       if (r == x) r = y;  // Save for return value.
  486.       left(p)   = y;
  487.       parent(y) = p;
  488.       color(y)  = color(x);
  489.       right(y)  = __copy(right(x), y);
  490.       p         = y;
  491.       x         = left(x);
  492.    }
  493.    left(p) = NIL;
  494.    return r;
  495. }
  496.  
  497. template <class Key, class Value, class KeyOfValue, 
  498.           class Compare, class Allocator>
  499. void rb_tree<Key, Value, KeyOfValue, Compare, Allocator>::__erase (link_type x)
  500. {
  501.     //
  502.     // Erase without rebalancing.
  503.     //
  504.     while (!isNil(x))
  505.     {
  506.        __erase(right(x));
  507.        link_type y = left(x);
  508.        put_node(x);
  509.        x = y;
  510.     }
  511. }
  512.  
  513. template <class Key, class Value, class KeyOfValue, 
  514.           class Compare, class Allocator>
  515. _TYPENAME rb_tree<Key, Value, KeyOfValue, Compare, Allocator>::iterator 
  516. rb_tree<Key, Value, KeyOfValue, Compare, Allocator>::erase (iterator first, 
  517.                                                       iterator locallast)
  518. {
  519.     iterator tmp = end();
  520.     if (first == begin() && locallast == end() && node_count != 0)
  521.     {
  522.         __erase(root());
  523.         leftmost()  = header;
  524.         root()      = NIL;
  525.         rightmost() = header;
  526.         node_count  = 0;
  527.         tmp = end();
  528.     } else
  529.     {
  530.         while (first != locallast) 
  531.           tmp =  erase(first++);
  532.     }
  533.     return tmp;
  534. }
  535.  
  536. template <class Key, class Value, class KeyOfValue, class Compare, class Allocator>
  537. void rb_tree<Key, Value, KeyOfValue, Compare, Allocator>::erase (const Key* first, 
  538.                                                       const Key* last)
  539. {
  540.     while (first != last) erase(*first++);
  541. }
  542.  
  543. template <class Key, class Value, class KeyOfValue, 
  544.           class Compare, class Allocator>
  545. _TYPENAME rb_tree<Key, Value, KeyOfValue, Compare, Allocator>::iterator 
  546. rb_tree<Key, Value, KeyOfValue, Compare, Allocator>::find (const Key& k)
  547. {
  548.     link_type y = header;  // Last node that is not less than k.
  549.     link_type x = root();  // Current node.
  550.  
  551.     while (!isNil(x))
  552.     {
  553.         if (!key_compare(key(x), k))
  554.             y = x, x = left(x);
  555.         else
  556.             x = right(x);
  557.     }
  558.     iterator j = iterator(y);
  559.     return (j == end() || key_compare(k, key(j.node))) ? end() : j;
  560. }
  561.  
  562. template <class Key, class Value, class KeyOfValue, 
  563.           class Compare, class Allocator>
  564. _TYPENAME rb_tree<Key, Value, KeyOfValue, Compare, Allocator>::const_iterator 
  565. rb_tree<Key, Value, KeyOfValue, Compare, Allocator>::find (const Key& k) const
  566. {
  567.     link_type y = header;  // Last node that is not less than k.
  568.     link_type x = root();  // Current node.
  569.  
  570.     while (!isNil(x))
  571.     {
  572.         if (!key_compare(key(x), k))
  573.             y = x, x = left(x);
  574.         else
  575.             x = right(x);
  576.     }
  577.     const_iterator j = const_iterator(y);   
  578.     return (j == end() || key_compare(k, key(j.node))) ? end() : j;
  579. }
  580.  
  581. template <class Key, class Value, class KeyOfValue, 
  582.           class Compare, class Allocator>
  583. _TYPENAME rb_tree<Key, Value, KeyOfValue, Compare, Allocator>::size_type 
  584. rb_tree<Key, Value, KeyOfValue, Compare, Allocator>::count (const Key& k) const
  585. {
  586.     pair<const_iterator, const_iterator> p = equal_range(k);
  587.     size_type n;
  588.     __initialize(n, size_type(0));
  589.     distance(p.first, p.second, n);
  590.     return n;
  591. }
  592.  
  593. template <class Key, class Value, class KeyOfValue, 
  594.           class Compare, class Allocator>
  595. _TYPENAME rb_tree<Key, Value, KeyOfValue, Compare, Allocator>::iterator 
  596. rb_tree<Key, Value, KeyOfValue, Compare, Allocator>::lower_bound (const Key& k)
  597. {
  598.     link_type y = header;  // Last node that is not less than k.
  599.     link_type x = root();  // Current node.
  600.  
  601.     while (!isNil(x))
  602.     {
  603.         if (!key_compare(key(x), k))
  604.             y = x, x = left(x);
  605.         else
  606.             x = right(x);
  607.     }
  608.  
  609.     return iterator(y);
  610. }
  611.  
  612. template <class Key, class Value, class KeyOfValue, 
  613.           class Compare, class Allocator>
  614. _TYPENAME rb_tree<Key, Value, KeyOfValue, Compare, Allocator>::const_iterator 
  615. rb_tree<Key, Value, KeyOfValue, Compare, Allocator>::lower_bound (const Key& k) const
  616. {
  617.     link_type y = header;  // Last node that is not less than k.
  618.     link_type x = root();  // Current node.
  619.  
  620.     while (!isNil(x))
  621.     {
  622.         if (!key_compare(key(x), k))
  623.             y = x, x = left(x);
  624.         else
  625.             x = right(x);
  626.     }
  627.  
  628.     return const_iterator(y);
  629. }
  630.  
  631. template <class Key, class Value, class KeyOfValue, 
  632.           class Compare, class Allocator>
  633. _TYPENAME rb_tree<Key, Value, KeyOfValue, Compare, Allocator>::iterator 
  634. rb_tree<Key, Value, KeyOfValue, Compare, Allocator>::upper_bound (const Key& k)
  635. {
  636.     link_type y = header;  // Last node that is greater than k.
  637.     link_type x = root();  // Current node.
  638.  
  639.     while (!isNil(x))
  640.     {
  641.         if (key_compare(k, key(x)))
  642.             y = x, x = left(x);
  643.         else
  644.             x = right(x);
  645.     }
  646.  
  647.     return iterator(y);
  648. }
  649.  
  650. template <class Key, class Value, class KeyOfValue, 
  651.           class Compare, class Allocator>
  652. _TYPENAME rb_tree<Key, Value, KeyOfValue, Compare, Allocator>::const_iterator 
  653. rb_tree<Key, Value, KeyOfValue, Compare, Allocator>::upper_bound (const Key& k) const
  654. {
  655.     link_type y = header;  // Last node that is greater than k.
  656.     link_type x = root();  // Current node.
  657.  
  658.     while (!isNil(x))
  659.     {
  660.         if (key_compare(k, key(x)))
  661.             y = x, x = left(x);
  662.         else
  663.             x = right(x);
  664.     }
  665.  
  666.     return const_iterator(y);
  667. }
  668.  
  669. template <class Key, class Value, class KeyOfValue, 
  670.           class Compare, class Allocator>
  671. _TYPENAME rb_tree<Key, Value, KeyOfValue, Compare, Allocator>::pair_iterator_iterator 
  672. rb_tree<Key, Value, KeyOfValue, Compare, Allocator>::equal_range (const Key& k)
  673. {
  674.     pair_iterator_iterator tmp(lower_bound(k), upper_bound(k));
  675.     return tmp;
  676. }
  677.  
  678. template <class Key, class Value, class KeyOfValue, 
  679.           class Compare, class Allocator>
  680. _TYPENAME rb_tree<Key, Value, KeyOfValue, Compare, Allocator>::pair_citerator_citerator 
  681. rb_tree<Key, Value, KeyOfValue, Compare, Allocator>::equal_range (const Key& k) const
  682. {
  683.     pair_citerator_citerator tmp(lower_bound(k), upper_bound(k));
  684.     return tmp;
  685. }
  686.  
  687.  
  688. #ifndef _RWSTD_NO_NAMESPACE
  689. }
  690. #endif
  691.  
  692. #pragma option pop
  693. #endif /* __TREE_CC */
  694.